package 背包问题01;

import java.util.Scanner;

/**
 * @Date 2024/10/4 21:12
 * @description: 01背包问题
 * .
 * @Author LittleNight
 */
public class niuke01 {


    /**
     * 不用恰好装满的情况.
     */
    // int N = 1010, n, V; // 表示物品和体积
    int[][] dp;
    public static void main(String[] args) {
        // 不用装满: 不用初始化.
        // 动态规划dp[i][j] 表示不超过j的容量，前i个物品的最大价值
        int[][] dp = new int[1001][1001];
        // 初始化, 进行读取个数
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), V = sc.nextInt(); // n 表示个数, V 表示背包容量
        // int[] v = new int[n];
        // int[] w = new int[n];
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for (int i = 1; i <= n; i++) { // 都是从 1 开始
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            // todo 注意这里是 <= V 而不是 n
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选第 i 个物品, 这个一定存在的
                if (j - v[i] >= 0) { // 选第 i 个物品, 要保证容量是够的
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);


        /**
         * 第二问.  恰好装满的情况.
         */
        for (int i = 0; i <= n; i++) {
            // todo 注意这里是 <= V 而不是 n
            for (int j = 0; j <= V; j++) {
                dp[i][j] = 0;
            }
        }
        // 注意这里初始化是 <= V. 而不是小于等于 V
        for (int j = 1; j <= V; j++) dp[0][j] = -1; // 初始化第一行

        // todo 主逻辑
        for (int i = 1; i <= n; i++) {
            // todo 注意这里是 <= V 而不是 n
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选, 这个就不用判断了, 假如前一个不能装满是 -1. 那么这个也是 -1. 所以就不用判断了
                if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1) {
                    dp[i][j] = Math.max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
                }
            }
        }
        // System.out.println(dp[n][n] == -1 ? 0 : dp[n][n]);
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}
